home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Tools / Languages / MacGofer 0.22d / MacGofer Sources / scc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-04-01  |  2.5 KB  |  64 lines  |  [TEXT/MPS ]
  1. /* --------------------------------------------------------------------------
  2.  * scc.c:       Copyright (c) Mark P Jones 1991-1993.   All rights reserved.
  3.  *              See goferite.h for details and conditions of use etc...
  4.  *              Gofer version 2.28 January 1993
  5.  *
  6.  * Strongly connected components algorithm for static.c.
  7.  * ------------------------------------------------------------------------*/
  8.  
  9. /* --------------------------------------------------------------------------
  10.  * Several parts of this program require an algorithm for sorting a list
  11.  * of values (with some added dependency information) into a list of strongly
  12.  * connected components in which each value appears before its dependents.
  13.  *
  14.  * The algorithm used here is based on those described in:
  15.  * 1) Robert Tarjan, Depth-first search and Linear Graph Algorithms,
  16.  *    SIAM J COMPUT, vol 1, no 2, June 1972, pp.146-160.
  17.  * 2) Aho, Hopcroft and Ullman, Design and Analysis of Algorithms,
  18.  *    Addison Wesley, 1972.  pp.189-195.
  19.  * The version used here probably owes most to the latter presentation but
  20.  * has been modified to simplify the algorithm and improve the use of space.
  21.  * ------------------------------------------------------------------------*/
  22.  
  23. static Int local LOWLINK Args((Cell));    /* local function           */
  24. static Int local LOWLINK(v)        /* calculate `lowlink' of v       */
  25. Cell v; {
  26.     Int  low = daCount;
  27.     Int  dfn = daCount;         /* depth first search no. of v       */
  28.     List ws  = DEPENDS(v);        /* adjacency list for v           */
  29.  
  30.     DEPENDS(v) = mkInt(daCount++);      /* push v onto stack           */
  31.     push(v);
  32.  
  33.     while (nonNull(ws)) {        /* scan adjacency list for v       */
  34.     Cell w = hd(ws);
  35.     ws     = tl(ws);
  36.     low    = sccMin(low, (visited(w) ? intOf(DEPENDS(w)) : LOWLINK(w)));
  37.     }
  38.  
  39.     if (low == dfn) {            /* start a new scc?           */
  40.     List temp=NIL;
  41.     do {                /* take elements from stack       */
  42.         DEPENDS(top()) = mkInt(0);
  43.         temp       = cons(top(),temp);
  44.     } while (pop()!=v);
  45.     daSccs = cons(temp,daSccs);    /* make new strongly connected comp*/
  46.     }
  47.  
  48.     return low;
  49. }
  50.  
  51. static List local SCC(bs)        /* sort list with added dependency */
  52. List bs; {                /* info into SCCs           */
  53.     clearStack();
  54.     daSccs = NIL;            /* clear current list of SCCs       */
  55.  
  56.     for (daCount=1; nonNull(bs); bs=tl(bs))     /* visit each binding       */
  57.     if (!visited(hd(bs)))
  58.         LOWLINK(hd(bs));
  59.  
  60.     return rev(daSccs);            /* reverse to obtain correct order */
  61. }
  62.  
  63. /*-------------------------------------------------------------------------*/
  64.